๋ฌธ์
Programmers - ๊ดํธ ํ์ ํ๊ธฐ
๐ Logic
// ์ฃผ์ด์ง ์ธ๋ฑ์ค ์ฌ์ด์ ๋ฌธ์์ด์ด ์ฌ๋ฐ๋ฅธ ๋ฌธ์์ด์ธ์ง ํ๋จ
private boolean isValid(int s, int e) {
if (s == e) return true;
for (int i = s; i < e; i++) {
char ch = str.charAt(i);
if (stack.isEmpty()) {
if (isCloseCh(ch)) return false;
stack.add(ch);
} else {
char stCh = stack.peek();
if (isPair(stCh, ch)) stack.pop();
else if (isCloseCh(ch)) return false;
else stack.add(ch);
}
}
return true;
}
- ์์ ์ธ๋ฑ์ค์ ๋ ์ธ๋ฑ์ค๋ฅผ ์ธ์๋ก ๋ฐ์, ํด๋น ์ธ๋ฑ์ค ์ฌ์ด์ ๋ฌธ์์ด์ด ์ฌ๋ฐ๋ฅธ์ง ํ์ธํ๋ ํจ์
- ์คํ์ ์ฌ์ฉํด ๊ดํธ ๋ฌธ์์ ์์ด ๋ง๋ค๋ฉด ์คํ์์ ์ ๊ฑฐํ๊ณ , ๊ทธ๋ ์ง ์๊ณ ๋ซํ ๊ดํธ๋ผ๋ฉด ์ฌ๋ฐ๋ฅด์ง ์์์ ๋ฐํํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Solution {
private String str;
private Stack<Character> stack;
public int solution(String s) {
this.str = s;
int len = s.length();
int answer = 0;
if (len % 2 == 1) return answer;
for (int i = 0; i < len; i++) {
stack = new Stack<>();
// i๋ถํฐ ๋ฌธ์์ด ๊ธธ์ด๊น์ง๊ฐ ์ฌ๋ฐ๋ฅด๋ค๋ฉด, 0๋ถํฐ i๊น์ง ์ฌ๋ฐ๋ฅธ์ง ํ์ธ
if (isValid(i, len))
answer += isValid(0, i) ? 1 : 0;
}
return answer;
}
// ์ฃผ์ด์ง ์ธ๋ฑ์ค ์ฌ์ด์ ๋ฌธ์์ด์ด ์ฌ๋ฐ๋ฅธ ๋ฌธ์์ด์ธ์ง ํ๋จ
private boolean isValid(int s, int e) {
if (s == e) return true;
for (int i = s; i < e; i++) {
char ch = str.charAt(i);
if (stack.isEmpty()) {
if (isCloseCh(ch)) return false;
stack.add(ch);
} else {
char stCh = stack.peek();
if (isPair(stCh, ch)) stack.pop();
else if (isCloseCh(ch)) return false;
else stack.add(ch);
}
}
return true;
}
private boolean isCloseCh(char ch) {
return ch == '}' || ch == ']' || ch == ')';
}
private boolean isPair(char stCh, char ch) {
return (stCh == '(' && ch == ')') || (stCh == '{' && ch == '}') || (stCh == '[' && ch == ']');
}
}
โ๏ธ Review
- ๊ดํธ๋ ํญ์ ์ง์ด ๋ง๋์ง์ ๋ํ ๋ก์ง์ด ํ์ํ๊ณ , ์ด๋ฅผ ๊ตฌํํ๊ธฐ ์ํด์๋ ์คํ์ด ์ ๊ฒฉ์ด๋ผ ์๊ฐํ๋ค.
- ๊ธ๋ฐฉ ํ๋ฆฐ ๋ฌธ์